package LinkedList.重排链表;

import LinkedList.ListNode;

/**
 * https://leetcode.cn/problems/reorder-list/description/
 */
public class Test {

    public void reorderList(ListNode head) {

        // 1. 找到中间节点
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 2. 反转后半部分
        ListNode mid = slow.next;
        slow.next = null;
        mid = reverse(mid);

        // 3. 合并两个链表
        ListNode p1 = head, p2 = mid;
        while(p1 != null && p2 != null) {
            ListNode next1 = p1.next, next2 = p2.next;
            p1.next = p2;
            p2.next = next1;
            p1 = next1;
            p2 = next2;
        }
    }

    // 反转函数
    private ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head, next;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
